package com.squirrel.michale;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/25 6:48 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0652 {

    Map<String, Integer> key2Id = new HashMap<>();
    List<TreeNode> resultList = new ArrayList<>();

    public List<TreeNode> findDuplicateSubtrees(TreeNode root) {
        getId(root);
        return resultList;
    }


    private String getId(TreeNode node) {
        if (node == null) {
            return "-1";
        }
        StringBuffer keyBuffer = new StringBuffer();
        keyBuffer.append(node.val).append("#").append(getId(node.left)).append("#").append(getId(node.right));
        String nodeKey = keyBuffer.toString();
        key2Id.put(nodeKey, key2Id.getOrDefault(nodeKey, 0) + 1);
        if (key2Id.get(nodeKey) == 2) {
            resultList.add(node);
        }
        return nodeKey;
    }
}
